package toOffer;

/**
 * <h3>leetcode</h3>
 *
 * @author BigFaceCat
 * @date 2024/1/25 15:14
 * @description <p>删除链表的倒数第 N 个结点</p>
 */


/**
 * 题目：给定一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
 */
public class toOffer4_3_21 {
    public static void main(String[] args) {
        ListNode node = null;
        int[] head = {1};
        int n = 1;
        for (int i = head.length - 1; i >= 0; i--) {
            node = new ListNode(head[i], node);
        }
        //输出
        ListNode newNode = removeNthFromEnd(node, n);
        while (newNode != null){
            System.out.print(newNode.getVal() + " ");
            newNode = newNode.next;
        }
    }

    /**
     * 使用双指针的方法。先令右指针指向第n个节点，再令左指针指向第一个节点。然后两个节点一起往链表后部移动
     * 当右指针指向最后一个节点的时候，左指针指向的就是倒数第n个节点
     *
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        //初始化哨兵节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        ListNode left = dummy;
        ListNode right = head;

        //先让right指针指向第n个节点
        for (int i = 0; i < n; i++) {
            right = right.next;
        }

        //同时移动左右指针
        while (right != null){
            right = right.next;
            left = left.next;
        }

        //删除倒数第n个节点
        left.next = left.next.next;
        return dummy.next;
    }

    /**
     * listNode实体类
     */
    public static class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        private int getVal(){
            return this.val;
        }
    }
}
